import sys
# Install gurobi
!{sys.executable} -m pip install -i https://pypi.gurobi.com gurobipy
!{sys.executable} -m pip install plotly geopy

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import pandas as pd
from itertools import product

import gurobipy as gp
from gurobipy import GRB, quicksum

# These are ours
import problem
import visualization

Looking in indexes: https://pypi.gurobi.com
Requirement already satisfied: gurobipy in /opt/anaconda3/lib/python3.8/site-packages (9.1.1)
Requirement already satisfied: plotly in /opt/anaconda3/lib/python3.8/site-packages (4.14.3)
Requirement already satisfied: geopy in /opt/anaconda3/lib/python3.8/site-packages (2.1.0)
Requirement already satisfied: six in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.15.0)
Requirement already satisfied: retrying>=1.3.3 in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.3.3)
Requirement already satisfied: geographiclib<2,>=1.49 in /opt/anaconda3/lib/python3.8/site-packages (from geopy) (1.50)

def normalize(i, j):
    assert i != j
    return (i, j) if i < j else (j, i)

Problem configuration

from model import Autonomax, Config

# Run on the first |C| cities (mostly for testing)
C = 41

# What scenario we will be utilizing
scenario = 0
# The number of cities in the core net
NC = 3
# 1 if the core net should be a cycle; 0 if it shoul be a path.
Z = 0

autonomax = Autonomax(
    Config(
        cities=problem.cities[:C],
        distances=problem.D[:C, :C],
        demand=problem.B[scenario][:C],
        core_city_count=NC,
        core_net_is_cycle=Z,
    )
)

Academic license - for non-commercial use only - expires 2021-05-15
Using license file /Users/sjurwold/gurobi.lic

A = autonomax.model.getA()

count = lambda d: len(d) if isinstance(d, gp.tupledict) else 1

V = sum(count(v) for v in autonomax.variables.values())
C = sum(count(c) for c in autonomax.constraints.values())

print(f'V = {V}, C = {C}')

fig, ax = plt.subplots(1, figsize=(128, 128 * C/V))
ax.set_xticklabels([])
ax.set_yticklabels([])
plt.spy(A)


total = 0
print(f'\nCONSTRAINT SETS:')
for (name, constraint) in autonomax.constraints.items():
    constraints_in_set = count(constraint)
    print(f'{constraints_in_set:>5} | {name}')
    #plt.gcf().text(0.07, 0.69 - 0.4 * (total + 0.5 * count(constraint)) / C, name, fontsize=14)
    total += constraints_in_set
    plt.plot([0, V], [total - 0.5, total - 0.5], color='grey')
    
total = 0
print(f'\nVARIABLE SETS:')
for (name, variables) in autonomax.variables.items():
    variables_in_set = count(variables)
    print(f'{variables_in_set:>5} | {name}')
    #plt.gcf().text(0.1 + 0.8 * (total + 0.5*count(variables)) / V, 0.8, name, fontsize=14)
    total += count(variables)
    plt.plot([total - 0.5, total - 0.5], [0, C], color='grey')
    
plt.savefig('constraint-matrix.png', dpi=200)

V = 7667, C = 5292

CONSTRAINT SETS:
    1 | one_control_center
   41 | control_city_directly_connected
 1681 | reduce_control_center_symmetry
   41 | core_city_ub
    1 | cycle_or_path
   41 | disallow_core_tree
    1 | exactly_nc_core_cities
   41 | control_center_is_connected
 1640 | is_connectable
   82 | is_connected_timestep
   41 | connected_graph
   41 | conservation_of_flow
  820 | force_edge_if_flow
  820 | edge_cost_lb

VARIABLE SETS:
   41 | is_control_center
  820 | is_core_edge
   41 | is_core_city
  123 | is_connected_step
 3362 | is_connectable_step
  820 | flow
  820 | abs_flow
  820 | is_sub_edge
  820 | edge_cost

autonomax.model.Params.timeLimit = 600.0
autonomax.model.optimize()

Changed value of parameter timeLimit to 600.0
   Prev: inf  Min: 0.0  Max: inf  Default: inf
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 5292 rows, 7667 columns and 25297 nonzeros
Model fingerprint: 0xe4067544
Model has 820 general constraints
Variable types: 2460 continuous, 5207 integer (5207 binary)
Coefficient statistics:
  Matrix range     [1e+00, 2e+05]
  Objective range  [1e+00, 2e+04]
  Bounds range     [1e+00, 1e+02]
  RHS range        [7e-01, 4e+01]
Presolve removed 89 rows and 1768 columns
Presolve time: 0.08s
Presolved: 5203 rows, 5899 columns, 25437 nonzeros
Variable types: 2460 continuous, 3439 integer (3439 binary)
Found heuristic solution: objective 73101.586734

Root relaxation: objective 7.420685e+02, 5480 iterations, 0.13 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0  742.06853    0  157 73101.5867  742.06853  99.0%     -    0s
H    0     0                    73060.052676  765.73809  99.0%     -    0s
     0     0 1663.98150    0  239 73060.0527 1663.98150  97.7%     -    0s
H    0     0                    42821.401419 1663.98150  96.1%     -    0s
     0     0 2080.32387    0  256 42821.4014 2080.32387  95.1%     -    0s
     0     0 2080.32387    0  257 42821.4014 2080.32387  95.1%     -    0s
     0     0 2080.32387    0  256 42821.4014 2080.32387  95.1%     -    0s
H    0     0                    23337.551631 2207.44607  90.5%     -    0s
     0     0 2207.44607    0  255 23337.5516 2207.44607  90.5%     -    0s
     0     0 2207.44607    0  236 23337.5516 2207.44607  90.5%     -    1s
H    0     0                    21087.311362 2207.44607  89.5%     -    1s
H    0     0                    18042.532077 2207.44607  87.8%     -    1s
     0     2 2207.44607    0  235 18042.5321 2207.44607  87.8%     -    1s
H   71    46                    17882.682740 2207.44607  87.7%   293    3s
H   73    46                    17785.839466 2207.44607  87.6%   290    3s
H  109    72                    16420.853426 2214.98583  86.5%   235    3s
H  111    72                    14753.726066 2214.98583  85.0%   233    3s
H  156   101                    14699.050959 2214.98583  84.9%   210    4s
H  158   101                    14657.581994 2214.98583  84.9%   212    4s
H  159   101                    14646.634271 2214.98583  84.9%   211    4s
   286   230 3932.61195   39  188 14646.6343 2214.98583  84.9%   150    5s
H  381   286                    14636.634271 2214.98583  84.9%   134    5s
H  383   286                    14634.156449 2214.98583  84.9%   133    5s
H  666   519                    14592.687484 2214.98583  84.8%   104    6s
  1537  1159 11700.5131   61  150 14592.6875 2214.98583  84.8%   100   10s
  1545  1168 2214.98583   15  311 14592.6875 2214.98583  84.8%   108   15s
  1681  1194 2742.98230   24  249 14592.6875 2742.98230  81.2%   123   20s
  2386  1261 3604.98409   35  247 14592.6875 2914.17691  80.0%   127   25s
  2946  1316 6571.71374   22  202 14592.6875 3217.19456  78.0%   139   30s
H 2951  1226                    14092.660686 3217.19456  77.2%   140   30s
H 2958  1221                    13960.022699 3217.19456  77.0%   140   30s
H 3004  1149                    13872.656843 3217.19456  76.8%   139   30s
H 3156  1112                    13861.477618 3590.91000  74.1%   139   31s
H 3158  1063                    13847.779356 3590.91000  74.1%   140   31s
H 3159  1017                    13836.577999 3590.91000  74.0%   140   31s
H 3160   971                    13826.577999 3590.91000  74.0%   140   31s
  3616  1055 6612.12142   34  139 13826.5780 3948.18207  71.4%   141   35s
  4353  1456 5604.28252   65  190 13826.5780 4765.65113  65.5%   139   40s
  5658  2167 9653.94092  125  181 13826.5780 5975.52342  56.8%   133   45s
H 5906  2245                    13799.273597 6269.72177  54.6%   133   45s
H 6423  2439                    13495.071643 6353.92326  52.9%   129   47s
H 6722  2605                    13461.226176 6353.92326  52.8%   130   49s
  6959  2721 11985.0867  107  132 13461.2262 7047.27087  47.6%   131   50s
  8716  3292 8501.02757   64  305 13461.2262 8124.44530  39.6%   132   55s
 11032  3859     cutoff   47      13461.2262 8984.53230  33.3%   132   60s
 13243  4099 9663.25726   37  204 13461.2262 9434.93514  29.9%   131   66s
 14745  4250 12247.2219   95  129 13461.2262 9779.39328  27.4%   131   72s
 15138  4156 10878.4041  111  132 13461.2262 9847.98410  26.8%   132   75s
 18527  3267     cutoff  116      13461.2262 10752.1356  20.1%   134   80s
 20390  1876     cutoff  125      13461.2262 11356.6986  15.6%   135   86s
 23091   247 infeasible  134      13461.2262 12818.7412  4.77%   129  100s

Cutting planes:
  Gomory: 40
  Cover: 105
  Implied bound: 12
  Clique: 1
  MIR: 66
  StrongCG: 2
  Flow cover: 131
  Inf proof: 5
  Zero half: 2
  RLT: 96
  Relax-and-lift: 11

Explored 27695 nodes (3021287 simplex iterations) in 101.08 seconds
Thread count was 8 (of 8 available processors)

Solution count 10: 13461.2 13495.1 13799.3 ... 14092.7

Optimal solution found (tolerance 1.00e-04)
Best objective 1.346122617578e+04, best bound 1.346122617578e+04, gap 0.0000%

Solution

city_info = pd.DataFrame(autonomax.city_info())
city_info

	Index	Name	IsCoreCity	IsControlCenter	Demand	IngoingFlow	OutgoingFlow
0	0	Boden	False	False	4.5	4.000000e+00	8.500000e+00
1	1	Borås	False	False	0.7	1.030000e+01	1.100000e+01
2	2	Eskilstuna	False	False	1.1	1.563194e-13	1.100000e+00
3	3	Falun	False	False	2.3	0.000000e+00	2.300000e+00
4	4	Gävle	False	False	1.0	4.020000e+01	4.120000e+01
5	5	Göteborg	False	False	5.8	1.350031e-13	5.800000e+00
6	6	Halmstad	False	False	3.4	6.100000e+00	9.500000e+00
7	7	Haparanda	False	False	4.6	0.000000e+00	4.600000e+00
8	8	Helsingborg	False	False	2.2	3.900000e+00	6.100000e+00
9	9	Hudiksvall	False	False	3.9	2.740000e+01	3.130000e+01
10	10	Jönköping	False	False	1.2	1.300000e+01	1.420000e+01
11	11	Kalmar	False	False	4.0	7.247536e-13	4.000000e+00
12	12	Karlskrona	False	False	1.6	2.771117e-13	1.600000e+00
13	13	Karlstad	False	False	0.9	2.844729e-10	9.000000e-01
14	14	Kiruna	False	False	4.0	1.563194e-13	4.000000e+00
15	15	Kristianstad	False	False	3.0	4.654055e-13	3.000000e+00
16	16	Lidköping	False	False	1.2	1.340000e+01	1.460000e+01
17	17	Linköping	False	False	4.1	1.800000e+00	5.900000e+00
18	18	Luleå	False	False	2.0	1.310000e+01	1.510000e+01
19	19	Malmö	False	False	2.6	1.300000e+00	3.900000e+00
20	20	Motala	False	False	2.4	5.900000e+00	8.300000e+00
21	21	Norrköping	False	False	1.7	1.769251e-12	1.700000e+00
22	22	Nyköping	False	False	4.6	8.597567e-13	4.600000e+00
23	23	Sandviken	True	False	4.5	4.350000e+01	4.800000e+01
24	24	Skellefteå	False	False	4.4	1.510000e+01	1.950000e+01
25	25	Skövde	True	False	2.5	3.980000e+01	4.230000e+01
26	26	Stockholm	False	False	7.0	8.455459e-13	7.000000e+00
27	27	Sundsvall	False	False	0.7	2.670000e+01	2.740000e+01
28	28	Trelleborg	False	False	1.3	1.371347e-12	1.300000e+00
29	29	Uddevalla	False	False	4.0	5.800000e+00	9.800000e+00
30	30	Umeå	False	False	3.2	1.950000e+01	2.270000e+01
31	31	Uppsala	False	False	1.9	7.000000e+00	8.900000e+00
32	32	Varberg	False	False	0.8	9.500000e+00	1.030000e+01
33	33	Vetlanda	False	False	2.1	1.090000e+01	1.300000e+01
34	34	Vänersborg	False	False	3.6	9.800000e+00	1.340000e+01
35	35	Västervik	False	False	1.8	2.465583e-12	1.800000e+00
36	36	Västerås	False	False	1.4	1.818989e-12	1.400000e+00
37	37	Växjö	False	False	2.3	4.600000e+00	6.900000e+00
38	38	Örebro	True	True	4.1	1.083000e+02	2.202682e-13
39	39	Örnsköldsvik	False	False	3.1	2.270000e+01	2.580000e+01
40	40	Östersund	False	False	0.9	1.007834e-10	9.000000e-01

edge_info = pd.DataFrame(autonomax.edge_info())
edge_info

	From	To	Type	Flow	Cost	Distance
0	Skellefteå	Umeå	SUB	19.5	731.139160	111
1	Skövde	Örebro	CORE	42.3	1320.000000	132
2	Gävle	Hudiksvall	SUB	-31.3	1278.724564	118
3	Karlskrona	Växjö	SUB	1.6	62.121900	102
4	Motala	Örebro	SUB	8.3	241.611348	92
5	Boden	Kiruna	SUB	-4.0	637.913000	291
6	Nyköping	Örebro	SUB	4.6	228.104575	131
7	Sundsvall	Östersund	SUB	-0.9	70.870188	166
8	Halmstad	Helsingborg	SUB	-6.1	145.447337	79
9	Jönköping	Vetlanda	SUB	-13.0	225.433574	65
10	Umeå	Örnsköldsvik	SUB	22.7	849.479945	111
11	Boden	Luleå	SUB	8.5	58.656839	32
12	Lidköping	Skövde	SUB	14.6	168.360541	49
13	Eskilstuna	Örebro	SUB	1.1	36.303275	83
14	Karlstad	Örebro	SUB	0.9	29.229970	77
15	Halmstad	Varberg	SUB	9.5	167.432227	65
16	Lidköping	Vänersborg	SUB	-13.4	206.938975	60
17	Uddevalla	Vänersborg	SUB	9.8	39.823253	21
18	Gävle	Sandviken	SUB	41.2	172.857299	25
19	Linköping	Motala	SUB	5.9	77.952787	51
20	Linköping	Västervik	SUB	-1.8	64.378861	97
21	Sundsvall	Örnsköldsvik	SUB	-25.8	1177.683887	127
22	Vetlanda	Växjö	SUB	-6.9	143.305429	72
23	Borås	Varberg	SUB	-10.3	260.758783	84
24	Haparanda	Luleå	SUB	4.6	210.858567	124
25	Luleå	Skellefteå	SUB	15.1	742.410242	133
26	Stockholm	Uppsala	SUB	7.0	136.873721	69
27	Kristianstad	Växjö	SUB	3.0	134.707658	120
28	Falun	Sandviken	SUB	2.3	48.115171	65
29	Norrköping	Örebro	SUB	1.7	72.868542	111
30	Gävle	Uppsala	SUB	-8.9	140.802752	60
31	Sandviken	Örebro	CORE	48.0	1790.000000	179
32	Helsingborg	Malmö	SUB	-3.9	67.318060	60
33	Göteborg	Uddevalla	SUB	5.8	117.417503	70
34	Malmö	Trelleborg	SUB	-1.3	18.150077	34
35	Jönköping	Skövde	SUB	14.2	337.352659	81
36	Hudiksvall	Sundsvall	SUB	-27.4	641.652314	81
37	Västerås	Örebro	SUB	1.4	49.705664	93
38	Borås	Skövde	SUB	11.0	384.262775	105
39	Kalmar	Vetlanda	SUB	4.0	174.202753	119

core_cost = sum(edge_info[edge_info['Type'] == 'CORE']['Cost'])
subnet_cost = sum(edge_info[edge_info['Type'] == 'SUB']['Cost'])
total_cost = core_cost + subnet_cost

print(f'core   = {core_cost:>9.3f}')
print(f'subnet = {subnet_cost:>9.3f}')
print('------------------')
print(f'total  = {total_cost:>9.3f}')
assert abs(autonomax.model.getObjective().getValue() - total_cost) < 1e-6

core   =  3110.000
subnet = 10351.226
------------------
total  = 13461.226

visualization.show(pd.DataFrame(autonomax.city_info()), pd.DataFrame(autonomax.edge_info()))